package com.lisp.algorithm.book.c16.q1_5;

public class Q1_5 {

	public static void main(String[] args) {
		Activity acts[] = new Activity[] {
			new Activity(0, 0, 0),
			new Activity(1, 5, 2),
			new Activity(6, 8, 4),
			new Activity(10, 30, 3),
			new Activity(30, 50, 4),
			new Activity(Integer.MAX_VALUE, 0, 0),
		};
		maxValue(acts);
	}

	// acts 已经按end排序
	public static void maxValue(Activity acts[]) {
		int len = acts.length;
		int solutions[][] = new int[len][len];
		
		for(int l=1; l<len; l++) {
			for(int i=0; i<len-l; i++) {
				int j=i+l;
				int max = 0;
				for(int k=i+1; k<=j; k++) {
					if(acts[k].start >= acts[i].end && acts[k].end <= acts[j].start) {
						int sum = solutions[i][k] + solutions[k][j] + acts[k].value;
						if(sum > max) {
							max = sum;
						}
					}
				}
				solutions[i][j] = max;
				System.out.println(String.format("solution[%s][%s]=%s", i, j, max));
			}
		}
	}
	
	static class Activity {
		int start;
		int end;
		int value;
		public Activity(int start, int end, int value) {
			this.start = start;
			this.end = end;
			this.value = value;
		}
	}
}
